package com.imooc.distributedemo.rithm;

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class ThreeNumAddDemo {

    /*标签：数组遍历
    首先对数组进行排序，排序后固定一个数 nums[i]nums[i]，再使用左右指针指向 nums[i]nums[i]后面的两端，数字分别为 nums[L]nums[L] 和 nums[R]nums[R]，计算三个数的和 sumsum 判断是否满足为 00，满足则添加进结果集
    如果 nums[i]nums[i]大于 00，则三数之和必然无法等于 00，结束循环
    如果 nums[i]nums[i] == nums[i-1]nums[i−1]，则说明该数字重复，会导致结果重复，所以应该跳过
    当 sumsum == 00 时，nums[L]nums[L] == nums[L+1]nums[L+1] 则会导致结果重复，应该跳过，L++L++
    当 sumsum == 00 时，nums[R]nums[R] == nums[R-1]nums[R−1] 则会导致结果重复，应该跳过，R--R−−
    时间复杂度：O(n^2)O(n2)，nn 为数组长度*/


    public static List<List<Integer>> threeNum(int[] nums){
        List<List<Integer>> ans = new ArrayList<>();
        int len = nums.length;

        if(nums == null||len < 3) {
            return ans;
        }
        Arrays.sort(nums); // 排序
        for (int i = 0; i < len; i++) {
            if(nums[i]>0) { // 如果当前数字大于0，则三数之和一定大于0，所以结束循环
                break;
            }
            if(i>0 && nums[i] == nums[i-1]){
                continue;  // 去重
            }
            // N个有序链表 分治法
            // 动态规划
            int L = i+1;
            int R = len-1;
            while (L < R){
                int sum = nums[i] + nums[L] +nums[R];
                if(sum == 0){
                    ans.add(Arrays.asList(nums[i],nums[L],nums[R]));
                    while (L < R && nums[L] == nums[L+1]) {
                        L++;
                    }
                    while(L < R && nums[R] == nums[R-1]){
                        R++;
                    }
                    L++;
                    R++;
                }else if(sum < 0){
                    L++;
                }else if(sum > 0){
                    R--;
                }
            }
        }
        return ans;
    }

    public static List<List<Integer>> threeNumAdd(int[] nums){
        Set<List<Integer>> ans = new HashSet<>();
        int len = nums.length;

        if(nums == null||len < 3) {
            return new ArrayList<>(ans);
        }
        Arrays.sort(nums);
        for (int i = 0; i < len; i++) {
            for (int j = i+1; j < len; j++) {
                for (int k = j+1; k < len; k++) {
                    if(nums[i]+nums[j]+nums[k]==0){
                        List<Integer> integers = Arrays.asList(nums[i], nums[j], nums[k]);
                        ans.add(integers);
                    }
                }
            }
        }
        return new ArrayList<>(ans);
    }

    public static void main(String[] args) {
        int[] nums = {-1,0,1,2,-1,-4};
        System.out.println(threeNumAdd(nums));
    }
}
